#pragma once
#include <allocators>

template<class HeapEleType, bool MAX_HEAP = true>
class Heap
{
public:
	Heap(): m_pArrHead(0), m_ArrSize(0), m_HeapSize(0), m_BufferSize(0) {
		Resize(10);
	}

	~Heap() {
		for (size_t i = 0; i != m_ArrSize; ++i) {
			(m_pArrHead + i)->~HeapEleType();
		}
		free(m_pArrHead);
	}

	Heap<HeapEleType> &Add(HeapEleType const &NewEle) {
		ResizeBuffer(1);
		m_pArrHead[m_ArrSize] = new(m_pArrHead + m_ArrSize) HeapEleType(NewEle);
		++m_ArrSize;
		++m_HeapSize;
		Heapify();
	}

private:
	void Heapify() {

	}

	inline void ResizeBuffer(size_t NewEleNum) {
		if (m_BufferSize < m_ArrSize + NewEleNum) {
			if (! Resize((m_ArrSize + NewEleNum) << 1)) {
				throw std::bad_alloc();
			}
		}
	}

	bool Resize(size_t NewEleNum) {
		if (NewEleNum < m_HeapSize) return false;
		HeapEleType *pNewArr = static_cast<HeapEleType*>(malloc(NewEleNum * sizeof(HeapEleType)));
		if (pNewArr == 0) return false;
		size_t CopyEleNum = NewEleNum < m_ArrSize ? NewEleNum : m_ArrSize;
		memcpy(pNewArr, m_pArrHead, CopyEleNum * sizeof(HeapEleType));
		free(m_pArrHead);
		m_pArrHead = pNewArr;
		m_ArrSize = CopyEleNum;
		m_BufferSize = NewEleNum;
		return true;
	}

private:
	HeapEleType *m_pArrHead;
	size_t m_ArrSize;
	size_t m_HeapSize;
	size_t m_BufferSize;
};